import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution2039 {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int[] first=new int[patience.length];
        Arrays.fill(first,-1);
        int count=0;
        int[] next=new int[edges.length*2];
        int[] go=new int[edges.length*2];
        for (int[] edge : edges) {
            next[count]=first[edge[0]];
            first[edge[0]]=count;
            go[count]=edge[1];
            count++;
            next[count]=first[edge[1]];
            first[edge[1]]=count;
            go[count]=edge[0];
            count++;
        }
        Queue<Integer> queue=new LinkedList<>();
        int[] visit=new int[patience.length];
        Arrays.fill(visit,Integer.MAX_VALUE/3);
        visit[0]=0;
        queue.offer(0);
        while (!queue.isEmpty()){
            int t=queue.poll();
            int k=first[t];
            while (k!=-1){
                int v=go[k];
                if (visit[v]==Integer.MAX_VALUE/3){
                    visit[v]=visit[t]+1;
                    queue.offer(v);
                }
                k=next[k];
            }
        }
        int time=0;
        for (int i=1;i<patience.length;i++){
            int total=visit[i]*2;
            int last=total%patience[i]!=0?total/patience[i]*patience[i]:total-patience[i];
            time=Math.max(time,last+visit[i]*2);
        }
        return time+1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution2039().networkBecomesIdle(new int[][]{{0,1},{1,2}},new int[]{0,2,1}));
    }
}
